package algorithmic_data_structure.单调栈;

import org.junit.Test;

import java.util.Stack;

public class Code06_子数组的最小值之和 {
    @Test
    public void test(){
        System.out.println(sumSubarrayMins(new int[]{3, 1, 2, 4}));
        System.out.println(sumSubarrayMins(new int[]{11,81,94,43,3}));
    }
    public static int sumSubarrayMins(int[] arr) {
        if(arr == null || arr.length == 0){
            return 0;
        }
        Stack<Integer> stack = new Stack<>();
        long res = 0;
        for (int index = 0; index < arr.length; index++) {
            while (!stack.isEmpty() && arr[index] <= arr[stack.peek()]){
                Integer pop = stack.pop();
                //leftSide 和 rightSide 都是取不到的
                long leftSide = stack.isEmpty() ? -1 : stack.peek();
                long rightSide = index;
                long leftCount = leftSide == -1 ? pop + 1 : pop - leftSide;
                long rightCount = rightSide - pop;
                res += ((rightCount * leftCount) * (long)arr[pop]);
                res %= 1000000007;
            }
            stack.push(index);
        }
        while (!stack.isEmpty()){
            Integer pop = stack.pop();
            long leftSide = stack.isEmpty() ? -1 : stack.peek();
            long rightSide = arr.length;
            long leftCount = leftSide == -1 ? pop + 1 : pop - leftSide;
            long rightCount = rightSide - pop;
//            res += (rightCount * leftCount) * arr[pop];
            res += ((rightCount * leftCount) * (long)arr[pop]);
            res %= 1000000007;
        }
        return (int) res;
    }
}
